A K-shortest paths algorithm is an algorithm solving the problem of obtaining a plurality of paths from specified source to destination nodes in the network topology. K paths which are sequenced from the small path weight summation to the large path weight summation can be obtained through this algorithm. The K-shortest paths algorithm is a very practical algorithm, which is widely applied in the fields such as the transportation, the communication routing calculation, the artificial intelligence, the economic theory research, and the mathematics application and so on. The K-shortest paths algorithm has very high application value, and can bring huge economic interests for users. For a long time, domestic and foreign academic circles have been deeply and widely researching the K-shortest paths algorithm, which aims to improve and enhance the efficiency of the algorithm, and reduce the time and space complexity of the algorithms as much as possible, thus many quite different K-shortest path algorithms emerged successively.
In recent years, along with the rapid development of the optical transport network Wavelength Switched Optical Network (WSON) technology, the K-shortest paths algorithm is more and more applied in solving the routing problem of the Routing and Wavelength Assignment (RWA) algorithm. Because the RWA itself has the non-deterministic polynomial feature, the inclusive R process for routing and the WA process for wavelength assignment should be implemented in two steps. The WA process of the WSON transport network in the prior art is generally not full wavelength switched. Because there is a limitation of the blocked cross restriction, K substitutable shortest paths need to be provided in the R process for routing calculation so that after the wavelength assignment (WA) fails in the selected path, substitutable paths can be provided to carry out the WA process over again. The RFC4655 and RFC4657 emphatically describe the function and architecture of the Path Computation Element (PCE) acting as the PCE of the Generalized Multiprotocol Label Switching (GMPLS). However, the problem of the K-shortest substitutable paths meeting the condition of the multiple edges between adjacent nodes is just a necessary function of the PCE in the condition of the WSON blocked cross.
In previous K-shortest paths algorithm documents, researchers usually only paid attention to the execution efficiency of the algorithm, and the research points in most cases were how to reduce the time and space complexity of the algorithm. However, few documents provide a thorough and detailed conclusion and summary on how to implement the K-shortest paths algorithm in different network topology scenarios. In the WSON networking environment, especially in the topological applications of multidimensional Reconfigurable Optical Add-Drop Multiplexer (ROADM) devices, the scenarios where there are multiple links between adjacent nodes often occur. Unfortunately, a great many known K-shortest paths algorithms at present usually requires the topographic to have a certain prerequisites:
1. the number of the sides m>=the number of the nodes n;
2. the weight of the sides w>0, and if the topographic is undirected, the bidirectional weights of sides should be equal;
3. the requirement for the directed or undirected topographic: some K-shortest paths algorithms definitely requires that they are only suitable for directed topographic.
4. the paths between any two nodes are not allowed to form a ring, namely, the paths do not include repeated nodes.
5. generally, the K-shortest paths algorithms are implemented based on the definition of the topographic: for the sides between adjacent nodes, the undirected topographic is restricted to have one directional side, and the directed topographic is restricted to have one side at most in positive direction and negative direction respectively (or a side exists in a certain direction, while no side exists in the other direction);
When K-shortest paths algorithms are implemented under the above prerequisites, a topographic scenario which is usually suitable for the calculation of the K-shortest paths algorithm is shown in FIG. 1.
However, in practical applications, there is often a case of multiple sides between adjacent nodes, as shown in FIG. 2. In this case, K-shortest paths algorithm generally cannot take other extra sides between the adjacent nodes into consideration, and only one side between adjacent nodes is reserved to participate in the calculation of the algorithm, and other sides are neglected and not participate in the calculation of the algorithm, and thereby the “K-shortest paths” calculated in such a way are not true K-shortest paths in the topology.